package 链表;

import java.util.ArrayList;

/**
 * https://leetcode-cn.com/leetbook/read/linked-list/fw8v5/
 * 
 * 你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。
 * 这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。
 * 给定链表的头节点head，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。
 * 子列表中的节点应该出现在扁平化列表中的curr 之后 和curr.next之前 。
 * 返回 扁平列表的 head。列表中的节点必须将其 所有 子指针设置为null。
 */
public class 扁平化多级双向链表 {
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    public Node flatten(Node head) {
        if(head == null) return head;
        ArrayList<Node> list = new ArrayList<>();
        Node tmp = head;
        inOrder(tmp,list); //装载完毕后，对集合中的节点进行操作
        if(list.size()>0){
            for (Node node : list) {
                //将每个节点原来的next,和child置为空，防止原先节点的child指针不为空，但是next也连着,连接上一个和下一个,重新串联
                node.prev = tmp;
                node.next = null;
                node.child = null;
                tmp.next = node;
                tmp = node;
            }
        }
        head.prev = null;
        head.child = null;
        return head;
    }

    //利用树的先序遍历，根左右，先子，在下，将节点装进一个集合中
    private void inOrder(Node tmp, ArrayList<Node> list){
        if(tmp == null) return;
        list.add(tmp);
        inOrder(tmp.child,list);
        inOrder(tmp.next,list);
    }
}
